class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        # 单调栈：栈中存单调递减的元素
        # 单调栈适用于找到*最近*出现的*更大/更小元素*的场景
        n = len(temperatures)
        stack = []
        res = [0] * n
        i = 0
        while i < n:
            if len(stack) == 0 or temperatures[i] <= temperatures[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                i_ = stack.pop()
                res[i_] = i - i_
        return res
